/*
 * @lc app=leetcode.cn id=1192 lang=cpp
 *
 * [1192] 查找集群内的关键连接
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    // 是关键连接等价于这条连接不在环内, 用访问时间的更新判断环
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        edgeNum_ = connections.size();
        nodeNum_ = n;
        graph_.resize(n, std::set<int>());
        
        // trans to neighbor list
        for (int i=0;i<edgeNum_;i++){
            int start = connections[i][0];
            int end = connections[i][1];
            graph_[start].emplace(end);
            graph_[end].emplace(start);
        }

        // init
        clock_ = -1;
        timeFirstVisitedDFS.resize(nodeNum_, -1);
        timeMinTraceBack_circleId.resize(nodeNum_, -1);

        // start circle searching
        circleSearchingTarjanDFS(0, 0);

        return result_;
    }
private:

/**
 * @brief 
 * 
 * Tarjan 算法基于 dfs
 * 求无向图的割点
 * 无向图的桥边（割边）
 * 无向图的双连通分量
 * 有向图的强连通分量
 * 
 * Tarjan 算法的关键点有二：
 * (1) 在 dfs 的过程中，记录每个节点初次被访问的时间戳
 * (2) 计算每个节点能访问到的节点的最小时间戳。
 * 
 */

    int clock_;
    vector<int> timeFirstVisitedDFS;
    vector<int> timeMinTraceBack_circleId;
    void circleSearchingTarjanDFS(int currentNode, int fromNode){
        clock_ ++;
        // 到了新结点先无脑打时间
        timeFirstVisitedDFS[currentNode] = clock_;
        timeMinTraceBack_circleId[currentNode] = clock_;

        for (auto neighbor : graph_[currentNode]){
            if (timeFirstVisitedDFS[neighbor] == -1){
                // new node found
                // 新结点先继续dfs走找更新的结点
                circleSearchingTarjanDFS(neighbor, currentNode);
                // 等回来了再统计是否更新环ID
                timeMinTraceBack_circleId[currentNode] = std::min(timeMinTraceBack_circleId[currentNode], timeMinTraceBack_circleId[neighbor]);
                
                // 判定 桥边 / 割边 
                if (timeMinTraceBack_circleId[neighbor] > timeFirstVisitedDFS[currentNode]){
                    vector<int> edge{currentNode, neighbor};
                    // how to avoid reversed edge ???
                    result_.emplace_back(edge);
                }
            // neighbor 在 current 前被访问过
            // 无向图 跳过 父节点
            }else if (timeFirstVisitedDFS[neighbor] < timeFirstVisitedDFS[currentNode] and neighbor != fromNode){

                // 为什么用 timeFirstVisitedDFS[neighbor] 不用 timeMinTraceBack_circleId[neighbor]
                // 在这场景二者都可以。
                // low[u] = Math.min(low[u], low[v]);

                // 找到的下个node是之前走过的node，此时把当前node环ID更新下
                timeMinTraceBack_circleId[currentNode] = std::min(timeMinTraceBack_circleId[currentNode], timeFirstVisitedDFS[neighbor]);
            }
        }
    }

    int edgeNum_;
    int nodeNum_;
    std::vector<std::set<int>> graph_;
    vector<vector<int>> result_;
};
// @lc code=end

int main(){
    // int n = 7;
    // vector<vector<int>> connections = {
    //     {0, 1},
    //     {2, 1},
    //     {0, 2},
    //     {2, 3},
    //     {3, 4},
    //     {3, 5},
    //     {4, 5},
    //     {4, 6}
    // };
    int n = 8;
    vector<vector<int>> connections = {
        {0, 1},
        {2, 1},
        {0, 2},
        {2, 7},
        {7, 3},
        {3, 4},
        {3, 5},
        {4, 5},
        {4, 6}
    };
    Solution test;
    test.criticalConnections(n, connections);
}

class SolutionViolent {
public:
    // 是关键连接等价于这条连接不在环内, 用访问时间的更新判断环
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        vector<vector<int>> res;
        
        edgeNum_ = connections.size();
        nodeNum_ = n;
        graph_.resize(n, std::set<int>());
        
        for (int i=0;i<edgeNum_;i++){
            int start = connections[i][0];
            int end = connections[i][1];
            graph_[start].emplace(end);
            graph_[end].emplace(start);
        }

        // back trace
        
        // check if the removed edge is substitutable
        for (int removeEdgeIndex = 0;removeEdgeIndex<edgeNum_;removeEdgeIndex++){
            int start = connections[removeEdgeIndex][0];
            int end = connections[removeEdgeIndex][1];
            graph_[start].erase(graph_[start].find(end));
            graph_[end].erase(graph_[end].find(start));

            if (!checkConnection(start, end)){
                res.emplace_back(connections[removeEdgeIndex]);
            }

            graph_[start].emplace(end);
            graph_[end].emplace(start);
        }

        return res;
    }
private:
    // void plotSet(std::set<int>& set);
    bool checkConnection(int node1, int node2){
        int start, end;
        if (graph_[node1] < graph_[node2]){
            start = node1;
            end = node2;
        }else{
            start = node2;
            end = node1;
        }

        std::set<int> reachable;
        std::queue<int> reachQueue;
        reachQueue.push(start);

        while (!reachQueue.empty()){
            int current = reachQueue.front();
            reachQueue.pop();
            
            auto& currentReach = graph_[current];
            for (int connectTo : currentReach){
                if (connectTo == end) {return true;}
                auto iter = reachable.find(connectTo);
                if (iter == reachable.end()){
                    reachable.emplace(connectTo);
                    reachQueue.push(connectTo);
                }
            }
        }
        return false;
    }

    int edgeNum_;
    int nodeNum_;
    std::vector<std::set<int>> graph_;
};